public class Test {
    public static void main(String[] args) {

    }
    //931.下降路径最小和
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix[0].length;
        if(n==1) {
            return matrix[0][0];
        }
        //1.创造dp数组，dp[i][j]代表到这个点的最小路径和
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++) dp[0][i] = matrix[0][i];
        for(int i = 1;i<n;i++) {
            for(int j = 0;j<n;j++) {
                if(j-1>=0 && j+1<=n-1) {
                    dp[i][j] = matrix[i][j]+Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]);
                }else if(j==n-1) {//右边界
                    dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j-1]);
                }else {//左边界
                    dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j+1]);
                }
            }
        }
        int min = dp[n-1][0];
        for(int i=1;i<n;i++) {
            if(dp[n-1][i] < min) min = dp[n-1][i];
        }
        return min;
    }
    //64.最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=1;i<n;i++) dp[0][i] = dp[0][i-1] + grid[0][i];
        for(int i=1;i<m;i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i][j-1],dp[i-1][j]);
            }
        }
        return dp[m-1][n-1];
    }
    //206.反转链表
//    public ListNode reverseList(ListNode head) {
//        if(head == null || head.next == null) return head;
//        ListNode newHead = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return newHead;
//    }


}
